/**
 * @version Create on 2012-11-13
 * @author Yinzi Chen
 */

public class ValidSudoku {

	int[][] map;
	boolean find;

	public void getCandi(int p, int q, int[] candi) {
		int x = p - p % 3, y = q - q % 3;
		boolean[] used = new boolean[10];
		for (int i = x; i < x + 3; ++i)
			for (int j = y; j < y + 3; ++j) {
				used[map[i][j]] = true;
			}
		for (int i = 0; i < 9; ++i) {
			used[map[i][q]] = true;
			used[map[p][i]] = true;
		}
		int top = 0;
		for (int i = 1; i < 10; ++i)
			if (!used[i])
				candi[top++] = i;
	}

	public void search(int p, int q) {
		if (p == 9 || find) {
			find = true;
			return;
		}
		if (map[p][q] != 0) {
			search(p + (q + 1) / 9, (q + 1) % 9);
		} else {
			int[] candi = new int[10];
			getCandi(p, q, candi);
			int i = 0;
			while (candi[i] != 0) {
				map[p][q] = candi[i];
				search(p + (q + 1) / 9, (q + 1) % 9);
				if (find)
					return;
				map[p][q] = 0;
				i++;
			}
		}
	}

	public boolean isValid() {
		for (int i = 0; i < 9; ++i)
			for (int j = 0; j < 9; ++j) {
				if (map[i][j] != 0) {
					int tmp = map[i][j];
					map[i][j] = 0;
					int[] candi = new int[10];
					getCandi(i, j, candi);
					int r = 0;
					while (candi[r] != 0 && candi[r] != tmp) {
						r++;
					}
					if (candi[r] == 0)
						return false;
					map[i][j] = tmp;
				}
			}
		return true;
	}

	public boolean isValidSudoku(char[][] board) {
		map = new int[9][9];
		for (int i = 0; i < 9; ++i)
			for (int j = 0; j < 9; ++j) {
				map[i][j] = (board[i][j] == '.' ? 0 : board[i][j] - '0');
			}
		if (!isValid())
			return false;
		return true;
	}

	public static void main(String[] args) {

	}
}
